/*
 * Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
 */
package com.xinpan.exercise;

import java.util.ArrayList;

public class RestoreIPAddress {
    public ArrayList<String> restoreIpAddresses(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> res = new ArrayList<String>();
        
        int i, j, k;
        
        for(i = 1; i < 4; i++)
        {
            if(s.length() - i <= 2)
                break;
                
            for(j = i+1; j < i+4; j++)
            {
                if(s.length() - j <= 1)
                    break;
                
                for(k = j+1; k < j+4; k++)
                {
                    if(s.length() - k == 0)
                        break;
                    if(s.length() - k > 3)
                        continue;
                    
                    String a = s.substring(0,i);
                    if(!legal(a))
                        continue;
                    String b = s.substring(i,j);
                    if(!legal(b))
                        continue;
                    String c = s.substring(j,k);
                    if(!legal(c))
                        continue;
                    String d = s.substring(k,s.length());
                    if(!legal(d))
                        continue;
                    
                    String ns = a + "." +
                                b + "." +
                                c + "." +
                                d;
                    res.add(ns);
                }
            }
        }
        return res;
    }
    
    public boolean legal(String s)
    {
        if(s.charAt(0) == '0' && s.length() > 1)
            return false;
        if(Integer.valueOf(s) > 255)
            return false;
        
        return true;
    }
}
